﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0197_FindDuplicateSubtrees : IAlgorithm
    {
        // 652. 寻找重复的子树

        /*
        给定一棵二叉树 root，返回所有重复的子树。
        对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
        如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

        提示：
            树中的结点数在[1,10^4]范围内。
            -200 <= Node.val <= 200
        */

        public void Test()
        {

        }

        // 算法
        Dictionary<string, Tuple<TreeNode, int>> seen = new Dictionary<string, Tuple<TreeNode, int>>();
        ISet<TreeNode> repeat = new HashSet<TreeNode>();
        int idx = 0;

        public IList<TreeNode> FindDuplicateSubtrees(TreeNode root)
        {
            DFS(root);
            return new List<TreeNode>(repeat);
        }

        public int DFS(TreeNode node)
        {
            if (node == null)
            {
                return 0;
            }
            Tuple<int, int, int> tri = new Tuple<int, int, int>(node.val, DFS(node.left), DFS(node.right));
            string hash = tri.ToString();
            if (seen.ContainsKey(hash))
            {
                Tuple<TreeNode, int> pair = seen[hash];
                repeat.Add(pair.Item1);
                return pair.Item2;
            }
            else
            {
                seen.Add(hash, new Tuple<TreeNode, int>(node, ++idx));
                return idx;
            }
        }
    }
}
